题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1505
仍然是决策单调性QAQ
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 100+9; const int MX = 100; double f[2][MAXN][MAXN],k1,k2; int n,m,sz[MAXN],sta=1; #define cal_up(l,r) (k1*((r)-(l))*((r)-(l))) inline double cal_down(int l, int r, int t){ int len = r-l, tmp = 0; double ret = 0; for (int i=1;i<=t;i++) sz[i] = len/t, tmp += sz[i]; while (tmp < len) for (int i=1;i<=t && tmp < len;i++) sz[i]++, tmp++; for (int i=1;i<=t;i++) ret += k2*sz[i]*sz[i]; return ret; } inline void Dynamic_Programing(int w, int t){ for (int i=1;i<=MX;i++) memset(f[w][i],0,sizeof(f[w][i])); for (int j=1,t1=1,t2=1;j<=n;j++,t1=1,t2=1) for (int i=1;i<=MX;i++) if (j <= i) { for (int h=max(1,t1-3);h<i;h++) for (int g=max(t2-3,1);g<j;g++) if (f[t][h][g]) { double tmp = f[t][h][g] + cal_up(h,i) + cal_down(h,i,j-g); if (!f[w][i][j] || f[w][i][j] > tmp) f[w][i][j] = tmp, t1=h, t2=g; } } } int main(){ scanf("%lf%lf%d%d",&k1,&k2,&m,&n); for (int i=1;i<=MX;i++) for (int j=1,lim=min(n,i);j<=lim;j++) f[1][i][j] = cal_up(0,i) + cal_down(0,i,j); for (int k=2;k<=m;k++,sta^=1) Dynamic_Programing(sta^1,sta); printf("%.1lf\n",f[sta][MX][n]); return 0; }
I too conceive therefore, perfectly written post! .
I think this is among the most vital info for me. And i am glad reading your article. But want to remark on some general things, The web site style is wonderful, the articles is really excellent : D. Good job, cheers